// ContourDistance.cpp: implementation of the CContourDistance class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include <math.h>
#include "ContourDistance.h"
#include "Point.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

const float EPSILON = 1.0e-5f;

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CContourDistance::CContourDistance(const SPoint *lpPoint, int nPoint, DISTANCE_TYPE eType)
{
	m_bIncludeHeadTail = FALSE;
	// may not to use, test case : u0001_20130222163256.chn
	m_bUseFastIndex = FALSE;

	m_pPoint = lpPoint;
	m_nPoint = nPoint;
	m_eType = eType;
	if (m_eType == DIST_DEFAULT)
		m_eType = DIST_NORMAL2;
	m_nLastIndex = -1;
}

CContourDistance::~CContourDistance()
{

}

///////////////////////////////////////////////////////////////////////////////

float CContourDistance::getDistance(const SPoint *ptCheck, int nCheck, float fAbortMaxValue)
{
	float fDist;
	switch(m_eType)
	{
	case DIST_NORMAL1:
		fDist = getNormal1Distance(ptCheck, nCheck, fAbortMaxValue);
		break;
	case DIST_NORMAL2:
		fDist = getNormal2Distance(ptCheck, nCheck, fAbortMaxValue);
		break;
	default:
		fDist = 0;
		break;
	}
	return fDist;
}

float CContourDistance::getNormal1Distance(const SPoint *ptCheck, int nCheck, float fAbortMaxValue)
{
	float f, f0;
	SFPoint ptInit = {(float)m_pPoint[0].x, (float)m_pPoint[0].y};
	float fDistSum = getMinimumDistanceOfPoint2Line(&ptInit, ptCheck, nCheck);
	if (fAbortMaxValue>0 && fDistSum>fAbortMaxValue)
		return fAbortMaxValue + 1000;
	SFPoint pt;
	for(int n=1; n<m_nPoint; n++)
	{
		SPoint pt0 = m_pPoint[n-1];
		SPoint pt1 = m_pPoint[n];
		int dx = pt1.x - pt0.x;
		int dy = pt1.y - pt0.y;
		int mMax = max(abs(dx), abs(dy));
		for(int m=1; m<mMax; m++)
		{
			f0 = m / (float)mMax;
			pt.x = pt0.x + f0 * dx;
			pt.y = pt0.y + f0 * dy;
			f = getMinimumDistanceOfPoint2Line(&pt, ptCheck, nCheck);
			fDistSum += f;
			if (fAbortMaxValue>0 && fDistSum>fAbortMaxValue)
				return fAbortMaxValue + 1000;
		}
	}
	return fDistSum;
}

float CContourDistance::getNormal2Distance(const SPoint *ptCheck, int nCheck, float fAbortMaxValue)
{
	int nIndex;
	float f, f0;
	float fCheck = (fAbortMaxValue>0 ? fAbortMaxValue*fAbortMaxValue : -1);
	SFPoint ptInit = {(float)m_pPoint[0].x, (float)m_pPoint[0].y};
	float fDistSquareSum = getMinimumDistanceSquareOfPoint2Line(&ptInit, ptCheck, nCheck, &nIndex);
	if (fCheck>0 && fDistSquareSum>fCheck)
		return fAbortMaxValue + 1000;
	BOOL fTail = FALSE;
	if (m_bIncludeHeadTail)
	{
		float f0 = getDistanceSquare(&ptInit, ptCheck);
		fDistSquareSum += f0;
		if (fCheck>0 && fDistSquareSum>fCheck)
			return fAbortMaxValue + 1000;
		SFPoint ptEnd = {(float)m_pPoint[m_nPoint-1].x, (float)m_pPoint[m_nPoint-1].y};
		float f1 = getDistanceSquare(&ptEnd, ptCheck+nCheck-1);
		fDistSquareSum += f1;
		if (fCheck>0 && fDistSquareSum>fCheck)
			return fAbortMaxValue + 1000;
		if (f0 < f1)
			fTail = TRUE;
	}
	SFPoint pt;
	if (fTail) {
		m_nLastIndex = nCheck - 1;
		for(int n=m_nPoint-1; n>0; n--)
		{
			SPoint pt0 = m_pPoint[n-1];
			SPoint pt1 = m_pPoint[n];
			int dx = pt1.x - pt0.x;
			int dy = pt1.y - pt0.y;
			int mMax = max(abs(dx), abs(dy));
			for(int m=mMax; m>0; m--)
			{
				f0 = m / (float)mMax;
				pt.x = pt0.x + f0 * dx;
				pt.y = pt0.y + f0 * dy;
				f = getMinDist2BackIndex(&pt, ptCheck, nCheck);
				fDistSquareSum += f;
				if (fCheck>0 && fDistSquareSum>fCheck)
					return fAbortMaxValue + 1000;
			}
		}
	} else {
		m_nLastIndex = 0;
		for(int n=1; n<m_nPoint; n++)
		{
			SPoint pt0 = m_pPoint[n-1];
			SPoint pt1 = m_pPoint[n];
			int dx = pt1.x - pt0.x;
			int dy = pt1.y - pt0.y;
			int mMax = max(abs(dx), abs(dy));
			for(int m=1; m<=mMax; m++)
			{
				f0 = m / (float)mMax;
				pt.x = pt0.x + f0 * dx;
				pt.y = pt0.y + f0 * dy;
				f = getMinDist2FromIndex(&pt, ptCheck, nCheck);
				fDistSquareSum += f;
				if (fCheck>0 && fDistSquareSum>fCheck)
					return fAbortMaxValue + 1000;
			}
		}
	}
	return sqrtf(fDistSquareSum);
}

float CContourDistance::getMinDist2BackIndex(const SFPoint *ptCheck, const SPoint *lpPoint, int nPoint)
{
	float f;
	int nMinIndex;
	if (m_bUseFastIndex)
	{
		int nFrom = max(m_nLastIndex-2, 0);
		f = getMinimumDistanceSquareOfPoint2Line(ptCheck, lpPoint+nFrom, min(3, nPoint-nFrom), &nMinIndex);
		m_nLastIndex = nFrom + nMinIndex;
	}
	else
	{
		f = getMinimumDistanceSquareOfPoint2Line(ptCheck, lpPoint, nPoint, &nMinIndex);
	}
	return f;
}

float CContourDistance::getMinDist2FromIndex(const SFPoint *ptCheck, const SPoint *lpPoint, int nPoint)
{
	float f;
	int nMinIndex;
	if (m_bUseFastIndex)
	{
		f = getMinimumDistanceSquareOfPoint2Line(ptCheck, lpPoint+m_nLastIndex, min(3, nPoint-m_nLastIndex), &nMinIndex);
		m_nLastIndex += nMinIndex;
	}
	else
	{
		f = getMinimumDistanceSquareOfPoint2Line(ptCheck, lpPoint, nPoint, &nMinIndex);
	}
	return f;
}

///////////////////////////////////////////////////////////////////////////////

float CContourDistance::getDistance(const SFPoint *pt1, const SPoint *pt2)
{
	float dx = pt2->x - pt1->x;
	float dy = pt2->y - pt1->y;
	return sqrtf((float)(dx * dx + dy * dy));
}

float CContourDistance::getDistanceSquare(const SFPoint *pt1, const SPoint *pt2)
{
	float dx = pt2->x - pt1->x;
	float dy = pt2->y - pt1->y;
	return (dx * dx + dy * dy);
}

float CContourDistance::getMinimumDistanceOfPoint2Line(const SFPoint *ptCheck, const SPoint *lpPoint, int nPoint)
{
	float fMinDist = getDistance(ptCheck, lpPoint);
	if (fMinDist < EPSILON)
		return 0;
	float f;
	for(int n=1; n<nPoint; n++)
	{
		SPoint pt0 = lpPoint[n-1];
		SPoint pt1 = lpPoint[n];
		if (pt0.x==pt1.x && pt0.y==pt1.y)
			continue;
		int dx = pt1.x - pt0.x;
		int dy = pt1.y - pt0.y;
		float m1 = (ptCheck->x - pt0.x) * dx + (ptCheck->y - pt0.y) * dy;
		if (m1 >= 0) {
			float m2 = (ptCheck->x - pt1.x) * (-dx) + (ptCheck->y - pt1.y) * (-dy);
			if (m2 >= 0) {
				// inner point
				float d = (ptCheck->x - pt0.x) * dy - (ptCheck->y - pt0.y) * dx;
				f = fabsf(d) / sqrtf((float)(dx * dx + dy * dy));
			} else {
				f = (float)getDistance(ptCheck, &pt1);
			}
		} else {
			f = (float)getDistance(ptCheck, &pt0);
		}
		fMinDist = min(fMinDist, f);
		if (fMinDist < EPSILON)
			return 0;
	}
	return fMinDist;
}

float CContourDistance::getMinimumDistanceSquareOfPoint2Line(const SFPoint *ptCheck, const SPoint *lpPoint, int nPoint, int *pnIndex)
{
	float fMinDistSquare = getDistanceSquare(ptCheck, lpPoint);
	if (fMinDistSquare < EPSILON)
	{
		*pnIndex = 0;
		return 0;
	}
	float f;
	int nMinIndex = -1;
	for(int n=1; n<nPoint; n++)
	{
		SPoint pt0 = lpPoint[n-1];
		SPoint pt1 = lpPoint[n];
		if (pt0.x==pt1.x && pt0.y==pt1.y)
			continue;
		int dx = pt1.x - pt0.x;
		int dy = pt1.y - pt0.y;
		float m1 = (ptCheck->x - pt0.x) * dx + (ptCheck->y - pt0.y) * dy;
		if (m1 >= 0) {
			float m2 = (ptCheck->x - pt1.x) * (-dx) + (ptCheck->y - pt1.y) * (-dy);
			if (m2 >= 0) {
				// inner point
				float d = (ptCheck->x - pt0.x) * dy - (ptCheck->y - pt0.y) * dx;
				f = (d * d) / (dx * dx + dy * dy);
			} else {
				f = getDistanceSquare(ptCheck, &pt1);
			}
		} else {
			f = getDistanceSquare(ptCheck, &pt0);
		}
		if (f < fMinDistSquare) {
			fMinDistSquare = f;
			nMinIndex = n - 1;
		}
		if (fMinDistSquare < EPSILON)
		{
			*pnIndex = n - 1;
			return 0;
		}
	}
	*pnIndex = nMinIndex;
	return fMinDistSquare;
}
